The present invention relates to forwarding of communications packets by a network multiplexer between separate communications network media coupled through the network multiplexer, and, in particular, to a method and system for guaranteeing maximum communications packet transit delays during communications packet forwarding by the network multiplexer.
Bridges, switches, and routers are all examples of network multiplexers. A network multiplexer forwards communications packets received from one communications network medium via a network multiplexer port to one or more destination communications media via one or more destination network multiplexer ports. Communications packets received by a network multiplexer are stored in memory of the network multiplexer and then forwarded to the destination ports. Message descriptors referencing the stored communications packet are placed into a transmit queue associated with each destination port. Many networking hardware and protocol standards, such as ethernet, require that a communications packet received by a network multiplexer be transmitted by the network multiplexer within some maximum transit delay period. In the case of the ethernet, the maximum transit delay is four seconds, but transit delays of not more than one second are recommended.
A problem in network multiplexers is that transmit queues can back up due to delays in transmitting queued packets by the transceiver associated with a port. For example, in the ethernet environment, a transmitter is required to wait for periods of increasing lengths following detection of packet collisions on the ethernet. It is often the case that the transceiver of a port associated with the transmit queue, following a back off or other transmission delay, cannot possibly transmit the remaining queued packets on the transmit queue within the maximum allowable transit delay for the most recently queued communications packets. Therefore, a method is required for identifying and discarding such stale packets from transmit queues. Currently-available methods include time stamps and local transmit timers within ports, but the former method may be expensive in terms of memory usage, and the latter method is unreliable. Therefore, network multiplexer designers, architects, and manufacturers have recognized the need for a memory-efficient and reliable method for ensuring that communications packets that cannot be forwarded in sufficient time to meet the maximum transmit delays are discarded.
The present invention provides a method and system for recognizing communications packets within a network multiplexer that cannot be forwarded to an appropriate network medium within a specified maximum transit delay time, so that these stale communications packets may be subsequently discarded. In the method and system of the present invention, a single flag bit is included in each message descriptor or queue entry in a transmit queue. When a message descriptor is initially placed into the queue, the flag bit is initially set to zero. A global system clock periodically awakens a transmit queue monitoring function that examines each entry queue in each transmit queue, setting each flag bit having the value xe2x80x9c0xe2x80x9d to xe2x80x9c1xe2x80x9d and discarding each queue entry, or message descriptor, having a flag bit already set to xe2x80x9c1.xe2x80x9d By this method, communications packets are not transmitted by the network multiplexer when they cannot reach their intended destination within a maximum transmit delay specified for the network medium through which the sending device is connected. By using only a single bit per queue entry, very little memory is used to implement the present invention.